#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
typedef long long LL;

#define LOCAL

int main() {
#ifdef LOCAL
  ifstream cin("C.in");
  ofstream cout("C.out");
  LL start = clock();
#endif
  ios::sync_with_stdio(false);

#ifdef LOCAL
  LL end = clock();
  cerr << 1.0 * (end - start) / CLOCKS_PER_SEC << endl;
#endif
  return 0;
}
/**
1003 odds 題解

這題是在樹 (tree) 上的一個問題，對於每一個葉節點 (leaf node)
要給出一個答案。這題可以在走訪 (traversal) 樹的過程中維護一些資料來求出解答。
PPP×\times× Q−1Q^{-1}Q​−1​​ modmodmod (109+7)(10^9 +
7)(10​9​​+7)

答案要求輸出一個整數 V=P×Q−1 mod (109+7)V = P \times Q ^ {-1} \ mod\ (10^9 +
7)V=P×Q​−1​​ mod (10​9​​+7)，其中 P/QP / QP/Q
為所求答案的最簡分數。這可以看作是一個避開浮點數評測問題的方法。因為模運算的緣故，我們可以只維護一個整數，這個整數在乘上一個浮點數的時候，直接乘上浮點數的分子再乘上浮點數分母的乘法反元素就好了。相似的，要除上一個浮點數時，可以乘上浮點數的分母，再乘上浮點數分子的乘法反元素即可。

至於找出乘法反元素的算法，網路上可以找到詳細的說明，這邊就不贅述。值得注意的是，這題中只會用到最大為
2×1052 \times 10^52×10​5​​
的反元素，先建表的話有機會可以節省一點點點時間。

以下我們將假設只需輸出浮點數來討論，以精簡題解的內容。
單一一個葉節點

對於單一一個葉節點，我們要做的事情其實是貪心的選擇從根 (root) 到此葉節點的路徑
(path) 上最有"效益"的 MMM 個節點，在此路徑上某個非葉節點 (non-leaf node)
對於在路徑上的那條邊的"效益"，指的就是這個非葉節點通往所有孩子
(不限定在此路徑上)
的邊的權重最大值除以在此路徑上的那條邊的權重，也就是說，如果在路經上的邊就已經擁有最大的權重的話，那效率就是
111，反之，我們都可以藉由選擇此節點交換邊來增加通往葉節點的機率。

我們可以在讀入輸入的時候就以 O(N)O(N)O(N)
的時間預處理，找出每個節點通往所有孩子的最大權重，所以對於一個單一節點的答案，就等價於找出這條路徑上前
MMM
大的效率值，再乘上原本到達這個葉節點的機率，即為答案。有一個小細節是，假設這條路徑不滿
MMM
個非葉點，那最好的狀況就是對每個非葉節點都進行操作，多出來的操作次數是沒有意義的。
一次處理所有葉節點

如果我們對於每個葉節點分開處理，那時間複雜度顯然會過高。一個可行的改進方法就是作一次深度優先的樹走訪，再走訪的過程中維護到目前這個節點為止，前
MMM 大的效率值。

在維護這 MMM 個值的時候，我們可以使用類似 c++ stl 中 multiset
的結構。在通過一條邊的時候，把此節點對於這條邊的效率值丟進 multiset 中，此時如果
multiset 中超過 MMM
個值，則把最小的值踢出，要注意此值要存起來。每當離開一條邊的時候，我們要把此節點對於這條邊的效率值從
multiset 中搜尋後移除，要注意不要一口氣把所有等於這個值的元素從 multiset
中移除，而是只能移除一個；並且，如果進入此節點時有剔除值，那這時就要把剔除的值加回去，以把
multiset 還原回進入此邊之前的樣貌。

此外要注意的是，在移除跟塞入值的時候，我們同時要維護前 MMM
大的值的乘積，不然對於每個葉節點都重新花 O(M)O(M)O(M)
的時間重算的話，複雜度也是不太行哦。
效率無限大的節點

在這題中有一個陷阱，也就是會存在權重為 000
的邊，這些節點的效率值會因為除以零的關係變成無限大。理論上我們的確是要最優先的選取這些邊，因為在路徑上只要有任一一條邊權重為
000，那到達此葉節點的機率也跟著是 000，但是，在維護 MMM
的乘積的同時會遇到一個麻煩，就是假如前 MMM
大的值有一個是無限大的話，乘積也就跟著為無限大，另外，假設一開始到達某葉節點的機率為
000，那後來乘上無限大的話，值就不知道怎麼算了。

因此，解決方法就是，在維護前 MMM 大的值的乘積的時候，我們把所有無限大的分母換成
2×1052 \times 10^52×10​5​​
再乘進去，這麼做的原因是，當我們選擇這條邊時，通往葉節點的機率將會從 000
變成其權重除以 2×1052 \times
10^52×10​5​​；並且，必須另外計數，維護到現在為止乘了幾個 (原來的)
無限大。同樣的，在計算一開始到達某葉節點的機率時，遇到權重 000
的邊，也不是直接乘進去，而是維護到底這個葉節點經過了多少條 000
的邊。到達某個葉節點的時候，如果這個葉節點的 000
邊數大於乘積中應有的無限大數量時，那到達這個葉節點的機率就還是
000，而如果這兩個計數相等，那機率就會是維護的乘積乘上到達這個葉節點的機率，因為每一條原來為
000 的邊都剛好被替換掉了。注意並不會有無限大的數量大於 000
邊的數量，大家可以想想為什麼。

整體時間複雜度為 O(NlogN)O(N\log N)O(NlogN)。
*/